import java.util.Arrays;

/**
 * @author TrinhNX 
 * http://en.wikipedia.org/wiki/Euler%27s_totient_function
 * http://primes.utm.edu/glossary/xpage/EulersPhi.html
 * One more better http://www.fq.math.ca/Scanned/11-1/brousseau.pdf
 */
/**
 * @author TrinhNX
 * @start_date 	: 20/04
 * @end_date	: 20/04 
 */
public class Euler026 {
	public static void main(String[] args) {
		// Wow, it is the largest prime number that smaller than 1000
		// Well, half right
		// It should be prime but no need to be largest :"<
		int i = 1000;
		int decimal = 0; // save the max decimal point
		final long start = System.currentTimeMillis();
		System.out.println("Start");
		while (--i > 1 && i > decimal) {
			if (Common.gcd(i, 10) == 1) {
				// We do the division here
				// 1/999 = 001
				int divisor = 1;
				// That convert our number
				int[] value = new int[i + 1];
				int index = 0;
				while (divisor < i) {
					divisor *= 10; // Multiple with 10
				}
				// Do division
				boolean check = true;
				int temp;
				while (check) {
					temp = divisor % i;
					Arrays.sort(value);
					// If not existed, add into the value
					if (Arrays.binarySearch(value, temp) < 0) {
						divisor = temp * 10;
						value[index++] = temp;
					} else {
						// If duplicated, move out
						check = false;
					}
				}
				// Ok now we get the index = the number of periods decimal
				// We compare this index number with previous, if bigger, updated
				// We also no need to check the value i that is smaller this index
				decimal = (index > decimal) ? index : decimal;
			}
		}
		System.out.println(i + 1);
		System.out.println("End after : " + (System.currentTimeMillis() - start));
		
	}
}
